Ch 5 Random Process

UTG

CPE 332

Computer Engineering

Mathematics II

Week 6

Part II, Chapter 5 Random Process

MarKov Process

Chapter 6: Introduction to Queuing

Today Topics

• Random Process

– Stationary: สถิติไม่เปลี่ยน

– Ergodic: Ensemble Average=Time

Average

– Autocorrelation

– Cross Correlation

• ต่อ

• Counting Process

• MarKov Process

Discrete-Time Random

Process

• อาจจะได ้จากการสุ่มตัวอย่าง (Sampling) ของ

Continuous RP

– Uniform Sampling ด ้วย Sampling Period 𝑇𝑇 = 1

𝑓𝑓𝑠𝑠

• เราได ้ … , X −T , 𝑋𝑋 0 , 𝑋𝑋 𝑇𝑇 , 𝑋𝑋 2𝑇𝑇 , 𝑋𝑋 3𝑇𝑇 , …

• ปกติจะละ Sampling Period ไว ้ฐานที่เข ้าใจ เราได ้

… , 𝑋𝑋 −1 , 𝑋𝑋 0 , 𝑋𝑋 1 , 𝑋𝑋 2 , 𝑋𝑋 3 , …

• มักจะเขียนในลักษณะ 𝑋𝑋 𝑛𝑛 ; 𝑛𝑛 = 𝑖𝑖𝑛𝑛𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖

𝑋𝑋(−8) 𝑋𝑋(−7) 𝑋𝑋(−6) 𝑋𝑋(−5) 𝑋𝑋(−4) 𝑋𝑋(−3) 𝑋𝑋(−2) 𝑋𝑋(−1)

𝑋𝑋(1) 𝑋𝑋(2) 𝑋𝑋(3) 𝑋𝑋(4) 𝑋𝑋(5) 𝑋𝑋(6)

𝑋𝑋(7)

𝑋𝑋(0)

จําก ัด Sequence ความยาว N

• ค่า Autocorrelation สําหรับ N Samples

– สมการจะลดรูป เหลือแค่ Sum และเฉลี่ย N

Point แต่จะเกิดการ Biased เพราะเราเฉลี่ย

น ้อยกว่านั้น

Sequence ท่ัวไป

મ઼��લ઼�

��દ્ધઙ્ખ Correlation

• 1. ด ้วยวิธีกราฟ

– X(n) คูณ X(n+m) คือ X(n) ที่เลื่อนไปซ ้าย m

ตําแหน่ง

• X(n-m) จะเลื่อนไปด ้านขวาแทน

– จากนั้นทําการคูณตัวอย่างที่ตําแหน่งเดียวกัน

และจับผลลัพธ์มาบวกกัน(Summation)

– ถ ้าเป็น Autocorrelation ทําแค่ครึ่งเดียว

เพราะ Rxx(m) เป็น Even Function

• Cross Correlation ต ้องทําทั้งสองด ้าน

મ઼��લ઼�

��દ્ધઙ્ખ Correlation

• 2. ด ้วยการแตก Summation

– 𝑅𝑅

𝑋𝑋𝑋𝑋 𝑚𝑚 = ∑𝑛𝑛=−∞ 𝑥𝑥 𝑛𝑛 𝑥𝑥(𝑛𝑛 + 𝑚𝑚) = 𝑅𝑅𝑋𝑋𝑋𝑋 −𝑚𝑚

– 𝑅𝑅

𝑋𝑋𝑌𝑌 ±𝑚𝑚 = ∑𝑛𝑛=−∞ 𝑥𝑥 𝑛𝑛 𝑦𝑦(𝑛𝑛 ± 𝑚𝑚), not Even

– Index ของ Summation จะสิ้นสุดแค่ Index ของ

x(n) ก็พอ เพราะที่เหลือจะเป็น ศูนย์

– เช่น x(n) = {2, 1, -1 ,3}, y(n) = {1,2,1,-1,-3,4,5}

-1 0 1 2

-3 -2 -1 0 1 2 3

– 𝑅𝑅

2

𝑋𝑋𝑋𝑋 2 = ∑𝑛𝑛=−1 𝑥𝑥 𝑛𝑛 𝑥𝑥 𝑛𝑛 + 2 = 𝑅𝑅𝑋𝑋𝑋𝑋 −2

• = 𝑥𝑥 −1 𝑥𝑥 1 + 𝑥𝑥 0 𝑥𝑥 2 + 𝑥𝑥 1 𝑥𝑥 3 + 𝑥𝑥 2 𝑥𝑥 4

• = 2 −1 + 1 3 + −1 ∙ 0 + 3 ∙ 0 = 1 = 𝑅𝑅𝑋𝑋𝑋𝑋(−2)

– 𝑅𝑅

2

𝑋𝑋𝑌𝑌(−1) = ∑𝑛𝑛=−1 𝑥𝑥 𝑛𝑛 𝑦𝑦 𝑛𝑛 − 1 ≠ 𝑅𝑅𝑋𝑋𝑌𝑌(1)

• = 𝑥𝑥 −1 𝑦𝑦 −2 + 𝑥𝑥 0 𝑦𝑦 −1 + 𝑥𝑥 1 𝑦𝑦 0 + 𝑥𝑥 2 𝑦𝑦 1

• = 2 ∙ 2 + 1 ∙ 1 + −1 ∙ −1 + 3 ∙ −3 = −3

Random Process મ઼�ઙ્ખ �

ઠ્ઠ �

હ્યદ્નદ્બ

• Counting Process

• Birth and Death Process

• Poisson Process

• MarKov Process

• MarKov Chain

Counting Process

N(t)

t

Poisson Process

Poisson Process

• ถ ้าแต่ละเหตุการณ์ที่เกิดขึ้นเป็น Random

และไม่ขึ้นต่อกัน มันจะเป็น Poisson

– Probability ที่จะมี k เหตุการณ์เกิดในช่วงเวลา

t สามารถคํานวณได ้จากสูตร (ดูหน้าถัดไป)

– ระยะเวลาระหว่างสองเหตุการณ์ที่เกิดขึ้น เรียก

Inter-arrival time, 𝜏𝜏, จะมีการกระจายแบบ

Exponential ด ้วยค่าเฉลี่ย 1/λ,

• 𝐹𝐹𝑋𝑋 𝜏𝜏 = 𝑃𝑃 𝑋𝑋 ≤ 𝜏𝜏 = 1−𝜆𝜆𝑒𝑒−𝜆𝜆𝜏𝜏, 𝑓𝑓𝑋𝑋 𝜏𝜏 = 𝜆𝜆𝑖𝑖−𝜆𝜆𝜏𝜏

Poisson Process

Birth and Death Process

State Diagram

• พิจารณาจากระบบ มีทั้ง Birth ด ้วย Birth Rate

λ( t) และ Death ด ้วย Death Rate µ( t)

– เมื่อเราให ้ระบบทํางาน ในระบบจะไม่มีอะไรอยู่ เรา

เรียกว่าอยู่ที่ State 0

– เมื่อมีหนึ่ง Event เข ้ามา หรือ Birth ระบบจะมี Event

เพิ่มขึ้นและจะไปอยู่ที่ State ที่มากกว่าปัจจุบัน “หนึ่ง”

– เมื่อมีหนึ่ง Event จบลง (Death) ระบบจะลด State ลง

หนึ่ง

– ค่า State ของระบบคือจํานวน Event ที่มีอยู่ในระบบ

– การกระโดดไปยัง State ที่สูงกว่า หรือตํ่ากว่า สามารถ

กําหนดด ้วย Probability และเขียนได ้ในลักษณะของ

State Diagram

• ถ ้าระบบไม่มีการจดจํา เราเรียก Diagram นี้เป็น MarKov Model

• ระบบคือ MarKov Process

• การ Transition จาก State หนึ่ง ไปอีก State หนึ่ง กําหนดได ้

โดยค่า Probability ที่คงที่

MarKov Process and Markov Chain

xn-2

x

n-1

x

n

xn+1

xn+2

Markov Process and Markov Chain

n-2

n-1

n

n+1

n+2

MarKov Chain

• สําหรับ MarKov Chain (Discrete State แต่

Time อาจจะเป็น Continuous หรือ Discrete)

– ในขั้นนี้ เราจะเน้นที่ Discrete Time Markov Chain

– สมมุติแกนเวลา ถูกแบ่งเป็น Time Slot ที่เท่ากัน

และเราอยู่ที่ State i ใน Time Slot ปัจจุบัน ดังนั้น

จะมีเหตุการณ์เกิดได ้ดังนี้

• ระบบอยู่ที่ State เดิม ใน Time Slot หน ้า ด ้วยค่า

Probability 𝑃𝑃𝑖𝑖𝑖𝑖

• ระบบมีการเปลี่ยน State ไปยัง State อื่นๆ ด ้วยค่า

Probability 𝑃𝑃𝑖𝑖𝑖𝑖; 𝑗𝑗 = 0,1,2, … , 𝑁𝑁, 𝑗𝑗 ≠ 𝑖𝑖

Note: Continuous Time MarKov Chain สามารถ Model จาก Discrete Time

MarKov Chain โดยให้ Limit ระยะห่างของ Time Slot เข้าสู่ศูนย์

Discrete Time Markov Chain

ในรูปไม่ได ้แสดง Transition หมดทุกเส ้น

𝑃𝑃0,4

𝑃𝑃0,3

𝑃𝑃0,2

𝑃𝑃0,0

𝑃𝑃1,1

𝑃𝑃2,2

𝑃𝑃3,3

𝑃𝑃4,4

𝑃𝑃

𝑃𝑃

𝑃𝑃

𝑃𝑃

0

0,1

3,4

1

1,2

2

2,3

3

4

𝑃𝑃1,0

𝑃𝑃2,1

𝑃𝑃3,2

𝑃𝑃4,3

𝑃𝑃2,0

𝑃𝑃4,0

𝑃𝑃3,0

Discrete Time Markov Chain

ถ้าระบบมีได้ถึง State N, (State 0,1,2,…,N),

Transition Matrix จะมีขนาด (N+1)คูณ(N+1)

Discrete Time Markov Chain

Notations: દ્ભ�દ્મ�� Discrete Time MarKov Chain

• State Probability

– คือ Probability ที่จะพบว่าระบบอยู่ที่ State ใดๆ

𝑝𝑝𝑖𝑖 = 𝑃𝑃𝑖𝑖𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑖𝑖𝑃𝑃𝑖𝑖𝑖𝑖𝑦𝑦 𝑆𝑆𝑖𝑖𝑃𝑃𝑖𝑖𝑖𝑖 = 𝑖𝑖, 𝑖𝑖 = 0,1, … , 𝑁𝑁

– ∑𝑁𝑁𝑥𝑥=0 𝑝𝑝𝑥𝑥 = 1

• Transition Probability

– คือ Probability ที่ระบบจะกระโดดจาก State

หนึ่งใน Time Slot ปัจจุบัน ไปยังอีก State หนึ่ง

ใน Time Slot หน ้า อย่าลืมว่าระบบไม่มีการจํา

– 𝑃𝑃𝑖𝑖𝑖𝑖 = 𝑃𝑃 𝑋𝑋𝑛𝑛 = 𝑖𝑖, 𝑋𝑋𝑛𝑛+1 = 𝑗𝑗 ; 𝑖𝑖, 𝑗𝑗 = 0,1, … , 𝑁𝑁

– ∑𝑁𝑁𝑖𝑖=0 𝑃𝑃𝑖𝑖𝑖𝑖 = 1

• ระบบอยู่ที่ Equilibrium ค่าเหล่านี้จะไม่เปลี่ยน

Discrete Time Markov Chain

Discrete Time Markov Chain

Discrete Time Markov Chain

Discrete Time Markov Chain

Discrete Time Markov Chain

สรุป MarKov Chain

• สถานะของระบบ ดูได ้จากจํานวณ Event ที่อยู่ในระบบ

เรียก State ของระบบ

– ถ ้า State เป็น Discrete เราได ้ MarKov Chain

• มีค่า Probability สองชุดที่อธิบายการทํางานของระบบ

– State Probability: Probability ที่ระบบจะอยู่ที่ State ใด

State หนึ่ง

• ผลรวมของ State Probability จะต ้องเท่ากับ 1

– Transition Probability: Probability ที่ระบบจะมีการเปลี่ยน

State

• อธิบายจาก Transition Matrix

• ผลรวมของ Transition Probability แต่ละแถว จะต ้องเท่ากับ 1

• ถ ้าระบบอยู่ที่ Equilibrium ค่า Probability ของ State

จะไม่เปลี่ยน และสามารถอธิบายได ้ด ้วย Global Balance

Equation

• MarKov Chain ที่เราสนใจคือ Irreducible และ

Aperiodic

Detailed Balance Equation:

Simple MarKov Chain

• Detailed Balance Equation

ระบบจะอยู่ที่ State เด ิม หร ือกระโดดไปย ัง State ข ้างเค ียงเท่าน ั�น

Markov Chain(Detailed Bal Eq)

• Detailed Balance Equation

• Transition Matrix ของ Simple Markov

Chain จะมีลักษณะเป็น Tridiagonal

P

P

0

00

01

P

P

P

10

11

12

P = 

P

P

P

21

22

23

Pn− ,1 n

 0

P

P

n, n−1

nn

Example

• MarKov Chain แสดงด ้วย Markov Model

ดังรูปข ้างล่าง

– 1. จงหา Transition Matrix

– 2. จาก Transition Matrix จงคํานวณหา State

Probability

0.2

0.3

0.1

0.2

0

1

2

3

0.1

0.1

0.2

0.5

0.8

0.6

0.6

0.1

0.2

Example

– 1. จงหา Transition Matrix

0.2

0.3

0.1

0.2

0

1

2

3

0.1

0.1

0.2

0.5

0.8

0.6

0.6

0.1

0.2

P

P

P

P

00

01

02

03 

P

P

P

P

10

11

12

13 

P =  P P P P

 20

21

22

23 

P

P

P

P

30

31

32

33 

Example

– 1. จงหา Transition Matrix

0.2

0.3

0.1

0.2

0

1

2

3

0.1

0.1

0.2

0.5

0.8

0.6

0.6

0.1

0.2

P

P

P

P

00

01

02

03 

 5

.

0

3

.

0

0

0 2

. 

 

P

P

P

P

10

11

12

13 

P =

=  1

.

0

0 8

.

0 1

.

0 

P

P

P

P

 1

.

0

.

0 1

6

.

0

0 2

. 

 20

21

22

23  

P

P

P

P

30

31

32

33 

 0

2

.

0

2

.

0

0 6

. 

Example

– 2. จงคํานวณหา State Probability

0.2

 5

.

0

0 3

.

0

.

0 2

0.3

0.1

0.2

0

1

2

3

P = 0 1

.

8

.

0

0 1

.

0 

0.1

0.1

0.2

0 1

.

1

.

0

0 6

.

.

0 2

0.5

0.8

0.6

0.6

0.1

0.2

 0

2

.

0

2

.

0

.

0 6

Example

– 2. จงคํานวณหา State Probability

0.2

 5

.

0

0 3

.

0

.

0 2

0.3

0.1

0.2

0

1

2

3

P = 0 1

.

8

.

0

0 1

.

0 

0.1

0.1

0.2

0 1

.

1

.

0

0 6

.

.

0 2

0.5

0.8

0.6

0.6

0.1

0.2

 0

2

.

0

2

.

0

.

0 6

p + p + p + p = 1 0

.

0

1

2

3

Global B

alanced Eq

uation :

p

P

p P

j

∑∞ =

ji

∑∞ i ij

i=0, ij

i=0, ij

Example

– 2. จงคํานวณหา State Probability

0.2

 5

.

0

0 3

.

0

.

0 2

0.3

0.1

0.2

0

1

2

3

P = 0 1

.

8

.

0

0 1

.

0 

0.1

0.1

0.2

0 1

.

1

.

0

0 6

.

.

0 2

0.5

0.8

0.6

0.6

0.1

0.2

 0

2

.

0

2

.

0

.

0 6

p + p + p + p =

0

.

1

0

1

2

3

Global B

alanced Eq

uation :

p

P

p P

j

∑∞ =

ji

∑∞ i ij

i=0, ij

i=0, ij

p [ P + P + P ] = p P + p P + p P

0

01

02

03

1 10

2

20

3 30

Example

– 2. จงคํานวณหา State Probability

0.2

 5

.

0

0 3

.

0

.

0 2

0.3

0.1

0.2

0

1

2

3

P = 0 1

.

8

.

0

0 1

.

0 

0.1

0.1

0.2

0 1

.

1

.

0

0 6

.

.

0 2

0.5

0.8

0.6

0.6

0.1

0.2

 0

2

.

0

2

.

0

.

0 6

p + p + p + p =

0

.

1

0

1

2

3

Global B

alanced Eq

uation : p [ P + P + P ] = p P + p P + p P

0

01

02

03

1 10

2

20

3

30

p

P

p P

p [ P + P + P ] = p P + p P + p P

j

∑∞ =

ji

∑∞ i ij

1

10

12

13

0

01

2

21

3

31

i=0, ij

i=0, ij

p [ P + P + P ] = p P + p P + p P

2

20

21

23

0

02

1 12

3

32

p [ P + P + P ] = p P + p P + p P

3

30

31

32

0

03

1 13

2

23

Example

– 2. จงคํานวณหา State Probability

0.2

 5

.

0

0 3

.

0

.

0 2

0.3

0.1

0.2

0

1

2

3

P = 0 1

.

8

.

0

0 1

.

0 

0.1

0.1

0.2

0 1

.

1

.

0

0 6

.

.

0 2

0.5

0.8

0.6

0.6

0.1

0.2

 0

2

.

0

2

.

0

.

0 6

p + p + p + p =

0

.

1

0

1

2

3

Global B

alanced Eq

uation :

p [ 3

.

0

+ 0 +

]

2

.

0

= 1

.

0 p +

1

.

0 p + .

0 p

0

1

2

3

p

P

p P

j

∑∞ =

ji

∑∞ i ij

p [ 1

.

0 +

1

.

0 + ]

0 =

3

.

0 p +

1

.

0 p +

2

.

0 p

i=0, ij

i=0, ij

1

0

2

3

p [ 1

.

0 +

1

.

0 +

]

2

.

0

= .

0 p + .

0 1 p + .

0 2 p

2

0

1

3

p [0 +

2

.

0

+

]

2

.

0

= 2

.

0 p + .

0 p +

2

.

0 p

3

0

1

2

Example

– 2. จงคํานวณหา State Probability

0.2

 5

.

0

0 3

.

0

.

0 2

0.3

0.1

0.2

0

1

2

3

P = 0 1

.

8

.

0

0 1

.

0 

0.1

0.1

0.2

0 1

.

1

.

0

0 6

.

.

0 2

0.5

0.8

0.6

0.6

0.1

0.2

 0

2

.

0

2

.

0

.

0 6

p + p + p + p =

0

.

1

0

1

2

3

Global B

alanced Eq

uation :

− 5

.

0 p + .

0 1 p + 0.1 p

= 0

0

1

2

p

P

p P

j

∑∞ =

ji

∑∞ i ij

.

0 3 p

2

.

0 p +

1

.

0 p +

2

.

0 p = 0

i=0, ij

i=0, ij

0

1

2

3

1

.

0 p

4

.

0 p +

2

.

0 p = 0

1

2

3

2

.

0 p

+ 0 2

. p

4

.

0 p = 0

0

2

3

Homogeneous Linear Eq. ยังแก้สมการไม่ได้

Example

– 2. จงคํานวณหา State Probability

0.2

 5

.

0

0 3

.

0

.

0 2

0.3

0.1

0.2

0

1

2

3

P = 0 1

.

8

.

0

0 1

.

0 

0.1

0.1

0.2

0 1

.

1

.

0

0 6

.

.

0 2

0.5

0.8

0.6

0.6

0.1

0.2

 0

2

.

0

2

.

0

.

0 6

− 5

.

0 p + .

0 1 p +

1

.

0 p

= 0

0

1

2

3

.

0 p − 0.2 p + .

0 1 p + .

0 2 p = 0

0

1

2

3

0 1

. p

4

.

0 p + 0.2 p = 0

1

2

3

p

+ p

+ p

+ p = .

1 0

0

1

2

3

ต ้องนําสมการที่ 4 มาใส่เสมอ + อีก 3 สมการอะไรก็ได ้

สมการ Non Homogeneous System of Linear Equation

แก ้ได ้โดยวิธี Elimination จะได ้ Unique Solution

Example

– 2. จงคํานวณหา State Probability

0.2

 5

.

0

0 3

.

0

.

0 2

0.3

0.1

0.2

0

1

2

3

P = 0 1

.

8

.

0

0 1

.

0 

0.1

0.1

0.2

0 1

.

1

.

0

0 6

.

.

0 2

0.5

0.8

0.6

0.6

0.1

0.2

 0

2

.

0

2

.

0

.

0 6

− 0 5

. p +

1

.

0 p + 0 1

. p

= 0

p

0

1

2

− 5

.

0

1

.

0

1

.

0

0  0 

0

   

.

0 3 p − 0 2

. p + 0 1

. p + .

0 2 p = 0

p

0

1

2

3

⇒  3

.

0

− 2

.

0

0 1

.

.

0 2 1 = 0

1

.

0 p − .

0 4 p + 0 2

. p = 0

 0

1

.

0

− 4

.

0

.

0 2 p

0

1

2

3

 2   

p

+ p

+ p

+ p = 1 0

.

p

0

1

2

3

 1

1

1

1  3  1

Non Homogeneous System of Linear Equation

แก ้ได ้โดยวิธี Elimination จะได ้ Unique Solution

Algorithm ในการแก ้สมการ จะกล่าวภายหล ัง

Example

– 2. จงคํานวณหา State Probability

0.2

 5

.

0

0 3

.

0

.

0 2

0.3

0.1

0.2

0

1

2

3

P = 0 1

.

8

.

0

0 1

.

0 

0.1

0.1

0.2

0 1

.

1

.

0

0 6

.

.

0 2

0.5

0.8

0.6

0.6

0.1

0.2

 0

2

.

0

2

.

0

.

0 6

− .

0 5 p +

1

.

0 p +

1

.

0 p

= 0

)

1

(

0

1

2

( )

4 − 5× ( )

2 : − .

0 5 p + 2 p + 0 5

. p = 1

)

5

(

.

0 3 p − 2

.

0 p +

1

.

0 p + .

0 2 p = 0

(2)

0

1

2

0

1

2

3

( )

4 − 5×

)

3

(

:

p + 0.5 p + 3 p = 1 ( )

6

1

.

0 p − 4

.

0 p +

2

.

0 p = 0

)

3

(

0

1

2

1

2

3

p

+ p

+ p

+ p = 0

.

1

( )

4

จากสมการที่ (1),(5),(6) เราได ้

0

1

2

3

− 0.5 p + 0.1 p + 0.1 p = 0

)

1

(

0

1

2

− 0.5 p + 2 p

+ 0.5 p = 1

)

5

(

0

1

2

p + 0.5 p + 3 p = 1 (6)

0

1

2

Example

– 2. จงคํานวณหา State Probability

0.2

 5

.

0

0 3

.

0

.

0 2

0.3

0.1

0.2

0

1

2

3

P = 0 1

.

8

.

0

0 1

.

0 

0.1

0.1

0.2

0 1

.

1

.

0

0 6

.

.

0 2

0.5

0.8

0.6

0.6

0.1

0.2

 0

2

.

0

2

.

0

.

0 6

− 0 5

. p + .

0 1 p +

1

.

0 p = 0

)

1

(

0

1

2

+ ×

p +

p =

(6) 2

)

1

( :

.

0 7

3 2

.

1 (7)

5

.

0 p + 2 p

+ 5

.

0 p = 1

)

5

(

1

2

0

1

2

(6) + 2 ×

)

5

(

:

.

4 5 p +

4 p = 3

)

8

(

p + .

0 5 p + 3 p = 1 ( )

6

1

2

0

1

2

5

.

4

4 5

.

4 5

.

)

8

(

(7) : (4 −

3 )

2

.

p = 3 −

0 7

.

0 7

.

2

0 7

.

− .

3 4285714

p =

= .

0 2069

2

− .

16 57142857

Example

– 2. จงคํานวณหา State Probability

0.2

 5

.

0

0 3

.

0

.

0 2

0.3

0.1

0.2

0

1

2

3

P = 0 1

.

8

.

0

0 1

.

0 

0.1

0.1

0.2

0 1

.

1

.

0

0 6

.

.

0 2

0.5

0.8

0.6

0.6

0.1

0.2

 0

2

.

0

2

.

0

.

0 6

p = 0 2069

.

2

1− .

3 2 p

From (7)

:

2

p =

= 0.4828

1

.

0 7

From )

1

( : p = 0.1379

0

From ( )

4 : p = .

0 1724

3

สมการ System of Linear Equation แก ้ได ้โดยวิธี Elimination p =

137

.

0

,

9 p = 0 482

.

,

8 p = 0 206

.

,

9 p = 0 172

.

4

0

1

2

3

Example: Simple MarKov

• MarKov Chain แสดงด ้วย Markov Model

ดังรูปข ้างล่าง

– 1. จงหา Transition Matrix

– 2. จาก Transition Matrix จงคํานวณหา

State Probability

0.5

0.1

0.3

0.2

0

1

2

3

4

0.1

0.2

0.2

0.6

0.5

0.8

0.5

0.6

0.4

Example: Simple MarKov

• Transition Matrix

0.5

0.1

0.3

0.2

0

1

2

3

4

0.1

0.2

0.2

0.6

0.5

0.8

0.5

0.6

0.4

P

P

P

P

P

0,0

0 1

,

0,2

0,3

0,4 

0 5

.

.

0 5

0

0

0 

 

P

P

P

P

P

,

1 0

1

,

1

,

1 2

,

1 3

,

1 4 

 .

0 1

.

0 8

1

.

0

0

0 

P ==  P

P

P

P

P  = 

2,0

2 1

,

2,2

2,3

2,4

0

0 2

.

0 5

.

.

0 3

0 

 

P

P

P

P

P

3,0

3 1

,

3,2

3,3

3,4 

 0

0

2

.

0

6

.

0

0 2

. 

P

P

P

P

P

 4,0

4 1

,

4,2

4,3

4,4 

 0

0

0

.

0 6

.

0 4

Example: Simple MarKov

• State Probability

0.5

0.1

0.3

0.2

0

1

2

3

4

0.1

0.2

0.2

0.6

0.5

0.8

0.5

0.6

0.4

P

P

P

P

P

0,0

0 1

,

0,2

0,3

0,4 

 5

.

0

5

.

0

0

0

0 

 

P

P

P

P

P

,

1 0

1

,

1

,

1 2

,

1 3

,

1 4 

 1

.

0

0 8

.

.

0 1

0

0 

P ==  P

P

P

P

P  = 

2,0

2 1

,

2,2

2,3

2,4

0

2

.

0

5

.

0

.

0 3

0 

 

P

P

P

P

P

3,0

3 1

,

3,2

3,3

3,4 

 0

0

.

0 2

6

.

0

.

0 2

P

P

P

P

P

4,0

4 1

,

4,2

4,3

4,4

0

0

0

.

0 6

4

.

0 

 

Detailed B

alance E

quation : p P = p P

i

i, j

j

j , i

p P = p P

.

0 5 p = .

0 1 p o

r p = 5 p

0 0 1

,

1

,

1 0

0

1

1

0

p P = p P

1

.

0 p = .

0 2 p o

r p = 0 5

. p = .

2 5 p

1

,

1 2

2

2 1

,

1

2

2

1

0

p P

= p P

3

.

0 p = .

0 2 p o

r p = .

1 5 p = .

3 75 p

2

2,3

3 3,2

2

3

3

2

0

1

p P

= p P

2

.

0 p = 0 6

. p o

r p =

p = .

1 25 p

3 3,4

4

4,3

3

4

4

3

3

0

Example: Simple MarKov

• State Probability

Detailed B

alance E

quation : p P = p P

i

i, j

j

j , i

p P = p P

.

0 5 p = .

0 1 p o

r p = 5 p

0 0 1

,

1

,

1 0

0

1

1

0

p P = p P

1

.

0 p = .

0 2 p o

r p = 0 5

. p = .

2 5 p

1

,

1 2

2

2 1

,

1

2

2

1

0

p P

= p P

3

.

0 p = .

0 2 p o

r p = .

1 5 p = .

3 75 p

2

2,3

3 3,2

2

3

3

2

0

1

p P

= p P

2

.

0 p = 0 6

. p o

r p =

p = .

1 25 p

3 3,4

4

4,3

3

4

4

3

3

0

From

p + p + p + p + p = 1

0

1

2

3

4

p + 5 p +

5

.

2 p + 3 75

.

p + .

1 25 p = 1

0

0

0

0

0

p 1

[ + 5 + 2 5

. +

75

.

3

+ .

1

]

25 = 1

0

p = 0 0740

.

74

then

0

p = 0 3703

.

,

7 p =

1851

.

0

,

85 p = .

0 2777

,

78 p = .

0 092593

1

2

3

4

Example: Simple MarKov

• State Probability

Detailed B

alance E

quation : p P = p P

i

i, j

j

j , i

p P = p P

.

0 5 p = .

0 1 p o

r p = 5 p

0 0 1

,

1

,

1 0

0

1

1

0

p P = p P

1

.

0 p = .

0 2 p o

r p = 0 5

. p = .

2 5 p

1

,

1 2

2

2 1

,

1

2

2

1

0

p P

= p P

3

.

0 p = .

0 2 p o

r p = .

1 5 p = .

3 75 p

2

2,3

3 3,2

2

3

3

2

0

1

p P

= p P

2

.

0 p = 0 6

. p o

r p =

p = .

1 25 p

3 3,4

4

4,3

3

4

4

3

3

0

From

p + p + p + p + p = 1

ใช้วิธีของ Matrix

0

1

2

3

4

0 5

. p

1

.

0 p = 0

p

0

1

0 5

.

− 1

.

0

0

0

0  0 

0

   

1

.

0 p − 0 2

. p = 0

p

1

2

 0

1

.

0

− 2

.

0

0

0  1 0

0 3

. p − 0 2

. p = 0

⇒  0

0

3

.

0

− .

0 2

0  p  = 0

2

3

 2  

.

0 2 p

6

.

0 p = 0

p

3

4

 0

0

0

2

.

0

− 6

.

0  3 0

p + p + p + p + p = 1

 1

1

1

1

1  p

 

0

1

2

3

4

 4 1

End of Chapter 5

• Chapter 6

– Introduction to Queuing Theory

• Homework Chapter 5 Download

– เน้นที่ Correlation ของ Stationary RP และ

การใช ้ Global/Detailed Balance Equation

ใน MarKov Chain

CPE 332

Computer Engineering

Mathematics II

Week 6

Part II, Chapter 6

Queuing System

Topics

• Birth and Death Process

• Unlimited Server

• N Servers

• Single Server, M/M/1

• Kendal Notation

• Applications

System

• ระบบประกอบด ้วย Input และ Output

• พิจารณาระบบที่มีการให ้บริการ(Service) แก่

ลูกค ้า (Customer)

– ลูกค ้าเข ้ามาในระบบเพื่อขอรับบริการ (Input)

– ระบบมี Resource ที่จํากัดในการให ้บริการ

– ลูกค ้า เมื่อได ้รับบริการแล ้ว ออกไปจากระบบ

(Output)

• ระบบขายของหน้าร ้าน, ระบบหน้าธนาคาร, ระบบ

การจราจร, ระบบ Operating System ใน

คอมพิวเตอร์, สถานีนํ้ามัน/แก๊ส, คิวจ่ายของ/

อาหาร, ระบบสื่อสารข ้อมูล, ระบบโทรศัพท์ และ

อื่นๆอีกมาก

Queuing System

Arrival Rate = λ

Departure Rate = µ

Customer

System

Customer

1. อ ัตร าการ เข ้ามาของลูกค ้า ค ือ Arrival Rate

2. อ ัตร าการ ออกไปของลูกค ้าเม ื่อได ้ร ับบร ิการ เสร็จค ือ Departure Rate

3. State ของร ะบบค ือจํานวนลูกค ้าที่อย ู่ในร ะบบ ที่ร อบร ิการ

หร ือกําล ังถูกบร ิการ

4. ถ ้าระบบไม่ม ีการจดจํา การบร ิการลูกค ้าแต่ละรายเหม ือนก ัน

และไม่ข ึ�นก ับอด ีต เราสามารถใช ้รูปแบบ MarKov Chain อธิบายระบบ

Queuing System

Birth Rate

Death Rate

Arrival Rate = λ

Departure Rate = µ

Customer

System

Customer

5. ถ ้าเราแบ่งช ่วงเวลาการเข ้ามาของลูกค ้าเป็นช ่วง Time Slot

และบ ันทึกเหตุการณ ์ที่เก ิดข ึ�นในแต่ละ Time Slot

a) ม ีลูกค ้าใหม ่เข ้ามา เพ ื่อขอใช ้บร ิการ ( State ของร ะบบจะเพ ิ่ม) หร ือ b) ม ีลูกค ้าที่ได ้ร ับบร ิการแล้วออกจากระบบไป ( State จะลด) หร ือ c) ไม่ม ีลูกค ้าใหม่ และไม่ม ีลูกค ้าที่ให้บร ิการเสร็จ (State คงเด ิม) 6. จาก Model ข ้อ 5 เราจะได ้ Discrete Time Markov Chain

7. ถ ้าช ่วงเวลาของ Time Slot ส ั�นมากจนกร ะท ่ังลูกค ้าที่เข ้ามา หร ือออกไป

ในช ่วงหน ึ่ง Time Slot สามารถม ีได ้แค่คนเด ียว

เราจะสามารถ Model ระบบได ้เป็น Simple MarKov Model

Queuing System

ถ ้า λ < µ ระบบจะสามารถ

เข ้าสู่ Equilibrium ได ้

Birth Rate

; Server Utilization Death Rate

𝜌𝜌 = 𝜆𝜆𝜇𝜇

Arrival Rate = λ

Departure Rate = µ

Customer

System

Customer

Queuing System

Simple MarKov Model

Birth Rate

Death Rate

λ < µ

Arrival Rate = λ

Departure Rate = µ

Customer

System

Customer

Detailed Balance Equation: 𝒑𝒑𝒊𝒊𝑷𝑷𝒊𝒊𝒊𝒊 = 𝒑𝒑𝒊𝒊𝑷𝑷𝒊𝒊𝒊𝒊

สําหร ับสอง State i, j ที่อยู่ต ิดก ันใดๆ

Queuing System

Simple MarKov Model

𝒑𝒑

Birth Rate

𝒊𝒊𝑷𝑷𝒊𝒊𝒊𝒊 = 𝒑𝒑𝒊𝒊𝑷𝑷𝒊𝒊𝒊𝒊

Death Rate

λ < µ

Arrival Rate = λ

Departure Rate = µ

Customer

System

Customer

ในที่นี�เราจะพ ิจารณ ากรณ ี

1.

ที่ลูกค ้าแต่ละรายเข ้ามาในระบบแบบ Random

และเป็น Poisson Process

2.

เวลาในการให้บร ิการของลูกค ้าแต่ละราย เป็น Random

ม ีการ กร ะจายแบบ Exponential

Queuing System

Simple MarKov Model

𝒑𝒑

Birth Rate

𝒊𝒊𝑷𝑷𝒊𝒊𝒊𝒊 = 𝒑𝒑𝒊𝒊𝑷𝑷𝒊𝒊𝒊𝒊

Death Rate

λ < µ

Arrival Rate = λ

Departure Rate = µ

Customer

System

Customer

Arrival: 1. Probability ที่จะม ีลูกค ้า k คนเข ้ามาในช ่วง T ว ินาที

(𝝀𝝀𝝀𝝀)𝒌𝒌𝒆𝒆𝝀𝝀𝝀𝝀

𝑷𝑷 𝒌𝒌 = 𝑷𝑷 𝑿𝑿 = 𝒌𝒌 =

𝒌𝒌!

; 𝒌𝒌 = 𝟎𝟎, 𝟏𝟏, 𝟐𝟐, …

เม ื่อ 𝝀𝝀 เป็นค ่าเฉลี่ยจํานวนลูกค ้าที่เข ้ามา ต ่อว ินาที

2. ค่า Inter-arrival Time, 𝝉𝝉 จะมีการกระจายแบบ

Exponential ด ้วยค ่าเฉล ี่ย 𝟏𝟏 𝝀𝝀

𝑷𝑷 𝝀𝝀 ≤ 𝝉𝝉 = 𝟏𝟏 − 𝝀𝝀𝒆𝒆−𝝀𝝀𝝉𝝉

Queuing System

Simple MarKov Model

𝒑𝒑

Birth Rate

𝒊𝒊𝑷𝑷𝒊𝒊𝒊𝒊 = 𝒑𝒑𝒊𝒊𝑷𝑷𝒊𝒊𝒊𝒊

Death Rate

λ < µ

Arrival Rate = λ

Departure Rate = µ

Customer

System

Customer

Departure: 1. เวลาเฉล ี่ยที่ลูกค ้าใช ้บร ิการ = 𝝀𝝀𝒔𝒔 (Service Time)

จะม ีการกระจายแบบ Exponential

Probability ที่ลูกค ้าจะใช ้เวลาบร ิการ น ้อยกว่าหร ือ

เท่าก ับ 𝒕𝒕 𝑷𝑷 𝝀𝝀 ≤ 𝒕𝒕 = 𝟏𝟏 − 𝟏𝟏 𝒆𝒆−𝒕𝒕 𝝀𝝀�𝒔𝒔

𝝀𝝀𝒔𝒔

2. Departure Rate ค ืออ ัตร าที่ลูกค ้าออกจากร ะบบ

เม ื่อได ้ร ับบร ิการเสร็จ(อ ัตราการให้บร ิการแก่ลูกค ้า)

𝝁𝝁 = 𝟏𝟏

𝝀𝝀𝒔𝒔

Queuing System Case 1:

Unlimited Server; No Queue

Arrival Rate = λ

Departure Rate = µ

Customer

System

Customer

1.

ลูกค ้าที่เข ้ามา เป็น Random ด ้วยอัตราเฉล่ีย 𝜆𝜆 และมีการกระจายแบบ Poisson 2.

สมมุติว่า Customer แต่ละคนที่เข ้ามาได ้รับการ Service จากระบบทันที (ระบบมี

Server จํานวนไม่จํากัด และรับ Customer ได ้ไม่จํากัด)

3.

เวลาที่ใช ้ในการ Service เป็น เป็น Exponential ด ้วยเวลาเฉล่ีย 𝑇𝑇𝑠𝑠

4.

ระบบสามารถรับ Customer ได ้ไม่จํากัด

5.

ลูกค ้าเข ้ามาได ้ทีละคน และออกทีละคน

6.

ระบบนี้เรียก M/M/∞

Queuing System Case 1:

Unlimited Server; No Queue

λ < µ

k

−λ

λ

x

e

ρ ρ

e

[

P k] =

λ

p =

; ρ =

t / Ts

1

[

P T

t] = e

; T =

k!

x

µ

s

µ

!

x

Arrival Rate = λ

Departure Rate = µ

Customer

System

Customer

1.

สมมุติว่า Customer แต่ละคนที่เข ้ามาเป็น Poisson และได ้รับการ Service จากระบบทันที

2.

เวลาที่ใช ้ในการ Service เป็น Random สมมุติว่าเป็น Exponential ด ้วยเวลาเฉลี่ย T

3.

ระบบสามารถรับ Customer ได ้ไม่จํากัด แต่เข ้ามาได ้ทีละคน และออกทีละคน

4.

ระบบนี้เรียก M/M/∞ แสดงได ้ด ้วย Simple Markov Model

5.

เราสามารถพิสูจน์ได ้ว่าค่า State Probability จะมีการกระจายแบบ Poisson p P = p P

i

ij

j

ji

0

1

2

i

j

Queuing System Case 2: Lost System

Limited Server=N; No Queue

λ < µ

x

ρ / x!

k

−λ

λ

p =

e

x

N

k

ρ

[

P k] =

t / Ts

1

[

P T

t] = e

; T =

k!

s

µ

!

0 k

k =

Arrival Rate = λ

Departure Rate = µ

Customer

System, N Server

Customer

1.

สมมุติว่า Customer แต่ละคนที่เข ้ามาเป็น Poisson และได ้รับการ Service จากระบบทันที

2.

เวลาที่ใช ้ในการ Service เป็น Random สมมุติว่าเป็น Exponential ด ้วยเวลาเฉลี่ย T

3.

ระบบสามารถรับ Customer ได ้ N ถ ้าทุก Server เต็ม จะรับ Customer ใหม่ไม่ได ้ (Lost) 4.

ระบบนี้เรียก M/M/N/N แสดงได ้ด ้วย N-state Simple Markov Model 5.

State Probability จะมีการกระจายแบบ First Erlang (Erlang B) Distribution p P = p P

i

ij

j

ji

0

1

2

i

j

N

Queuing System Case 3: Delay System

Limited Server=N; With Unlimited Queue

x

ρ

λ < µ

p ; 0 ≤ x N

1

0

N

1



k

!

x

Nρ

ρ 

k

−λ

λ

p =

p

x

x

=

+

N

N

e

; 0

ρ

[

P k] =

N

N!( N − ρ)

k

k =

!

t / T

0

s

1

  p ; x N

[

P T

t] = e

; T =

k!

s

0

µ

 N!  N

Arrival Rate = λ

Departure Rate = µ

Customer

System, N Server

Customer

1.

สมมุติว่า Customer แต่ละคนที่เข ้ามาเป็น Poisson และได ้รับการ Service จากระบบทันที

2.

เวลาที่ใช ้ในการ Service เป็น Random สมมุติว่าเป็น Exponential ด ้วยเวลาเฉลี่ย T

3.

ระบบสามารถรับ Customer ได ้ไม่จํากัด แต่จะ Service ได ้สูงสุด N พร ้อมๆกัน

4.

ถ ้าทุก Server เต็ม Customer ใหม่จะต ้องรอใน Queue ในกรณีนี้จะเกิด Queuing Delay 5.

ระบบนี้เรียก M/M/N หรือ M/M/N/∞ แสดงได ้ด ้วย Simple Markov Model 6.

State Probability จะมีการกระจายแบบ Second Erlang (Erlang C) Distribution

0

1

2

N

N+1

p P = p P

i

ij

j

ji

Queuing System Case 3: Delay System

Server=1; With Unlimited Queue; M/M/1

λ < µ 1

 ρ

−

p =

+1

=1− ρ

0

k

−λ

λ

 − ρ

e

1

(

)

[

P k] =

t / Ts

1

x

[

P T

t] = e

; T =

k!

s

p = ρ 1

( − ρ)

µ

x

Arrival Rate = λ

Departure Rate = µ

Customer

System, 1 Server

Customer

1.

สมมุติว่า Customer แต่ละคนที่เข ้ามาเป็น Poisson และได ้รับการ Service จากระบบทันที

2.

เวลาที่ใช ้ในการ Service เป็น Random สมมุติว่าเป็น Exponential ด ้วยเวลาเฉลี่ย T

3.

ระบบสามารถรับ Customer ได ้ไม่จํากัด แต่จะ Service ได ้ครั้งละคน

4.

ถ ้าทุก Server เต็ม Customer ใหม่จะต ้องรอใน Queue ในกรณีนี้จะเกิด Queuing Delay 5.

ระบบนี้เรียก M/M/1 หรือ M/M/1/∞ แสดงได ้ด ้วย Simple Markov Model 6.

State Probability จะมีการกระจายแบบ Second Erlang (Erlang C) Distribution

0

1

2

i

j

p P = p P

i

ij

j

ji

Queuing System: Model

S

S

Service Rate

Arrival Rate = λ

= µ=1/Ts

Customer

S

Queue(FIFO)

Customer

S

M/M/N

Queuing System

Servers

M/M/1: Summary

λ

µ=1/Ts

S

Arrival = Poisson, λ

Inter Arrival Time = Exponential, 1/λ

Service Rate, µ

Service Time, Ts (1/µ) = Exponential

Queue = FIFO

1 Server

Queuing Model(1 Server);

M/M/1

Queue = 0, No Delay

Queue = Delay

0

1

N+1

N+2

X

Server ว่าง Server Busy

1/Ts = service rate

arrival rate

For each server

λ

µ =1/ Ts

การทํางานของ M/M/1

State = 0

No Q Delay

Queue Empty

State = 1

Delay

State = x; Queue = infinity

Customer Wait in Q

State = x; x = Q+1

Severe Delay

Queue Overflow (Full)

กรณีที่

Congestion

Queue มีขนาดจํากัด = Q

Packet Lost

เปรียบเทียบ Queuing Model

(N Server); M/M/N

Queue = 0, No Delay

Queue = Delay

0

1

i

j

N

N+1

N+2

X

Server ว่าง

i Server Busy

N Server Busy

1 Server Busy

1/h = service rate

A/h=arrival rate

For each server

Maximum Service Rate

= N/h

Service Rate at State

k = k/h

M/M/N

State < N

No Delay

Queue Empty

State >= N

Delay

Customer Wait in Q

Limited Q

Severe Delay

Queue Overflow (Full)

Congestion

Network Model using

M/M/1

แต่ละ Router เชื่อมต่อกันด ้วย Logical Link เดียว

เสมือนว่ามี Transmitter ตัวเดียวในการส่งข ้อมูลผ่าน Link

Network Model (M/M/1)

สมมุติว่าคอมพิวเตอร์ที่ต่อกับ Router

ต ้องการส่งข ้อมูลถึงกัน ตามเส ้นทางที่กําหนด

Network Model (M/M/1)

ที่ Output ของ Router สามารถ Model โดยใช ้ M/M/1

Network Model (M/M/1)

ถ ้าเราให ้ทุก Model เป็น M/M/1

ดังนั้น Delay จะเป็นผลรวมของ Delay แต่ละอัน

Kendal Notation

Kendal Notation

Kendal Notation

Next Week

• M/M/1 Analysis and Examples

• HW 5 Due

Document Outline

Table of contents

previous page start